import java.util.Iterator;
import java.util.NavigableMap;
import java.util.TreeMap;

/*
        3.2 How would you design a stack which, in addition to push and pop, also has a
        function min which returns the minimum element? Push, pop and min should   all operate in O(1) time.
    */
public class StackWithMin<T extends Comparable<T>> implements Stack<T> {
    StackImpl<T> stack = new StackImpl<T>();
    NavigableMap<T, Integer> minMap = new TreeMap<T, Integer>();

    public StackWithMin(T[] values) {
        for (T value : values) {
            push(value);
        }
    }

    public int getNumberOfElements() {
        return stack.pointer;
    }

    public T getElementAt(int index) {
        return stack.getElementAt(index);
    }

    public boolean isEmpty() {
        return stack.isEmpty();
    }

    public T pop() {
        final T element = stack.pop();
        minMap.remove(element);
        return element;
    }

    public void push(T element) {
        final Iterator<T> iterator = minMap.keySet().iterator();
        if (iterator.hasNext()) {
            T currentMin = iterator.next();
            if (element.compareTo(currentMin) < 0) {
                minMap.put(element, stack.pointer);
            }
        } else {
            minMap.put(element, 0); // The first record
        }
        stack.push(element);
    }

    @Override
    public T peek() {
        return stack.peek();
    }

    public T getMinimum() {
        if (stack.isEmpty()) return null;
        return minMap.keySet().iterator().next();
    }
}